home *** CD-ROM | disk | FTP | other *** search
/ PC PowerPlay 58 / pcpp58a.iso / extras / quake 3 source / Q3A_ToolSource.exe / Main / compress.c < prev    next >
Encoding:
C/C++ Source or Header  |  2001-01-02  |  13.4 KB  |  751 lines
  1. #include "q3data.h"
  2.  
  3. #if 0
  4. /*
  5. ==================
  6. MTF
  7. ==================
  8. */
  9. cblock_t MTF (cblock_t in)
  10. {
  11.     int            i, j, b, code;
  12.     byte        *out_p;
  13.     int            index[256];
  14.     cblock_t    out;
  15.  
  16.     out_p = out.data = malloc(in.count + 4);
  17.  
  18.     // write count
  19.     *out_p++ = in.count&255;
  20.     *out_p++ = (in.count>>8)&255;
  21.     *out_p++ = (in.count>>16)&255;
  22.     *out_p++ = (in.count>>24)&255;
  23.  
  24.     for (i=0 ; i<256 ; i++)
  25.         index[i] = i;
  26.  
  27.     for (i=0 ; i<in.count ; i++)
  28.     {
  29.         b = in.data[i];
  30.         code = index[b];
  31.         *out_p++ = code;
  32.         
  33.         // shuffle b indexes to 0
  34.         for (j=0 ; j<256 ; j++)
  35.             if (index[j] < code)
  36.                 index[j]++;
  37.         index[b] = 0;
  38.     }
  39.  
  40.     out.count = out_p - out.data;
  41.  
  42.     return out;
  43. }
  44.  
  45.  
  46. //==========================================================================
  47.  
  48. int        bwt_size;
  49. byte    *bwt_data;
  50.  
  51. int bwtCompare (const void *elem1, const void *elem2)
  52. {
  53.     int        i;
  54.     int        i1, i2;
  55.     int        b1, b2;
  56.  
  57.     i1 = *(int *)elem1;
  58.     i2 = *(int *)elem2;
  59.  
  60.     for (i=0 ; i<bwt_size ; i++)
  61.     {
  62.         b1 = bwt_data[i1];
  63.         b2 = bwt_data[i2];
  64.         if (b1 < b2)
  65.             return -1;
  66.         if (b1 > b2)
  67.             return 1;
  68.         if (++i1 == bwt_size)
  69.             i1 = 0;
  70.         if (++i2 == bwt_size)
  71.             i2 = 0;
  72.     }
  73.  
  74.     return 0;
  75. }
  76.  
  77. /*
  78. ==================
  79. BWT
  80. ==================
  81. */
  82. cblock_t BWT (cblock_t in)
  83. {
  84.     int        *sorted;
  85.     int        i;
  86.     byte    *out_p;
  87.     cblock_t    out;
  88.  
  89.     bwt_size = in.count;
  90.     bwt_data = in.data;
  91.  
  92.     sorted = malloc(in.count*sizeof(*sorted));
  93.     for (i=0 ; i<in.count ; i++)
  94.         sorted[i] = i;
  95.     qsort (sorted, in.count, sizeof(*sorted), bwtCompare);
  96.  
  97.     out_p = out.data = malloc(in.count + 8);
  98.  
  99.     // write count
  100.     *out_p++ = in.count&255;
  101.     *out_p++ = (in.count>>8)&255;
  102.     *out_p++ = (in.count>>16)&255;
  103.     *out_p++ = (in.count>>24)&255;
  104.  
  105.     // write head index
  106.     for (i=0 ; i<in.count ; i++)
  107.         if (sorted[i] == 0)
  108.             break;
  109.     *out_p++ = i&255;
  110.     *out_p++ = (i>>8)&255;
  111.     *out_p++ = (i>>16)&255;
  112.     *out_p++ = (i>>24)&255;
  113.  
  114.     // write the L column
  115.     for (i=0 ; i<in.count ; i++)
  116.         *out_p++ = in.data[(sorted[i]+in.count-1)%in.count];
  117.  
  118.     free (sorted);
  119.  
  120.     out.count = out_p - out.data;
  121.  
  122.     return out;
  123. }
  124.  
  125. //==========================================================================
  126.  
  127. typedef struct hnode_s
  128. {
  129.     int            count;
  130.     qboolean    used;
  131.     int            children[2];
  132. } hnode_t;
  133.  
  134. int            numhnodes;
  135. hnode_t        hnodes[512];
  136. unsigned    charbits[256];
  137. int            charbitscount[256];
  138.  
  139. int    SmallestNode (void)
  140. {
  141.     int        i;
  142.     int        best, bestnode;
  143.  
  144.     best = 99999999;
  145.     bestnode = -1;
  146.     for (i=0 ; i<numhnodes ; i++)
  147.     {
  148.         if (hnodes[i].used)
  149.             continue;
  150.         if (!hnodes[i].count)
  151.             continue;
  152.         if (hnodes[i].count < best)
  153.         {
  154.             best = hnodes[i].count;
  155.             bestnode = i;
  156.         }
  157.     }
  158.  
  159.     if (bestnode == -1)
  160.         return -1;
  161.  
  162.     hnodes[bestnode].used = true;
  163.     return bestnode;
  164. }
  165.  
  166. void BuildChars (int nodenum, unsigned bits, int bitcount)
  167. {
  168.     hnode_t    *node;
  169.  
  170.     if (nodenum < 256)
  171.     {
  172.         if (bitcount > 32)
  173.             Error ("bitcount > 32");
  174.         charbits[nodenum] = bits;
  175.         charbitscount[nodenum] = bitcount;
  176.         return;
  177.     }
  178.  
  179.     node = &hnodes[nodenum];
  180.     bits <<= 1;
  181.     BuildChars (node->children[0], bits, bitcount+1);
  182.     bits |= 1;
  183.     BuildChars (node->children[1], bits, bitcount+1);
  184. }
  185.  
  186. /*
  187. ==================
  188. Huffman
  189. ==================
  190. */
  191. cblock_t Huffman (cblock_t in)
  192. {
  193.     int            i;
  194.     hnode_t        *node;
  195.     int            outbits, c;
  196.     unsigned    bits;
  197.     byte        *out_p;
  198.     cblock_t    out;
  199.     int            max, maxchar;
  200.  
  201.     // count
  202.     memset (hnodes, 0, sizeof(hnodes));
  203.     for (i=0 ; i<in.count ; i++)
  204.         hnodes[in.data[i]].count++;
  205.  
  206.     // normalize counts
  207.     max = 0;
  208.     maxchar = 0;
  209.     for (i=0 ; i<256 ; i++)
  210.     {
  211.         if (hnodes[i].count > max)
  212.         {
  213.             max = hnodes[i].count;
  214.             maxchar = i;
  215.         }
  216.     }
  217.     if (max == 0)
  218.         Error ("Huffman: max == 0");
  219.  
  220.     for (i=0 ; i<256 ; i++)
  221.     {
  222.         hnodes[i].count = (hnodes[i].count*255+max-1) / max;
  223.     }
  224.  
  225.     // build the nodes
  226.     numhnodes = 256;
  227.     while (numhnodes != 511)
  228.     {
  229.         node = &hnodes[numhnodes];
  230.  
  231.         // pick two lowest counts
  232.         node->children[0] = SmallestNode ();
  233.         if (node->children[0] == -1)
  234.             break;    // no more
  235.  
  236.         node->children[1] = SmallestNode ();
  237.         if (node->children[1] == -1)
  238.         {
  239.             if (node->children[0] != numhnodes-1)
  240.                 Error ("Bad smallestnode");
  241.             break;
  242.         }
  243.         node->count = hnodes[node->children[0]].count + 
  244.             hnodes[node->children[1]].count;
  245.         numhnodes++;
  246.     }
  247.  
  248.     BuildChars (numhnodes-1, 0, 0);
  249.  
  250.     out_p = out.data = malloc(in.count*2 + 1024);
  251.     memset (out_p, 0, in.count*2+1024);
  252.  
  253.     // write count
  254.     *out_p++ = in.count&255;
  255.     *out_p++ = (in.count>>8)&255;
  256.     *out_p++ = (in.count>>16)&255;
  257.     *out_p++ = (in.count>>24)&255;
  258.  
  259.     // save out the 256 normalized counts so the tree can be recreated
  260.     for (i=0 ; i<256 ; i++)
  261.         *out_p++ = hnodes[i].count;
  262.  
  263.     // write bits
  264.     outbits = 0;
  265.     for (i=0 ; i<in.count ; i++)
  266.     {
  267.         c = charbitscount[in.data[i]];
  268.         bits = charbits[in.data[i]];
  269.         while (c)
  270.         {
  271.             c--;
  272.             if (bits & (1<<c))
  273.                 out_p[outbits>>3] |= 1<<(outbits&7);
  274.             outbits++;
  275.         }
  276.     }
  277.  
  278.     out_p += (outbits+7)>>3;
  279.  
  280.     out.count = out_p - out.data;
  281.  
  282.     return out;
  283. }
  284.  
  285. //==========================================================================
  286.  
  287. /*
  288. ==================
  289. RLE
  290. ==================
  291. */
  292. #define    RLE_CODE    0xe8
  293. #define    RLE_TRIPPLE    0xe9
  294.  
  295. int    rle_counts[256];
  296. int    rle_bytes[256];
  297.  
  298. cblock_t RLE (cblock_t in)
  299. {
  300.     int        i;
  301.     byte    *out_p;
  302.     int        val;
  303.     int        repeat;
  304.     cblock_t    out;
  305.  
  306.     out_p = out.data = malloc (in.count*2);
  307.  
  308.     // write count
  309.     *out_p++ = in.count&255;
  310.     *out_p++ = (in.count>>8)&255;
  311.     *out_p++ = (in.count>>16)&255;
  312.     *out_p++ = (in.count>>24)&255;
  313.  
  314.     for (i=0 ; i<in.count ; )
  315.     {
  316.         val = in.data[i];
  317.         rle_bytes[val]++;
  318.         repeat = 1;
  319.         i++;
  320.         while (i<in.count && repeat < 255 && in.data[i] == val)
  321.         {
  322.             repeat++;
  323.             i++;
  324.         }
  325. if (repeat < 256)
  326. rle_counts[repeat]++;
  327.         if (repeat > 3 || val == RLE_CODE)
  328.         {
  329.             *out_p++ = RLE_CODE;
  330.             *out_p++ = val;
  331.             *out_p++ = repeat;
  332.         }
  333.         else
  334.         {
  335.             while (repeat--)
  336.                 *out_p++ = val;
  337.         }
  338.     }
  339.  
  340.     out.count = out_p - out.data;
  341.     return out;
  342. }
  343.  
  344. //==========================================================================
  345.  
  346. unsigned    lzss_head[256];
  347. unsigned    lzss_next[0x20000];
  348.  
  349. /*
  350. ==================
  351. LZSS
  352. ==================
  353. */
  354. #define    BACK_WINDOW        0x10000
  355. #define    BACK_BITS        16
  356. #define    FRONT_WINDOW    16
  357. #define    FRONT_BITS        4
  358. cblock_t LZSS (cblock_t in)
  359. {
  360.     int        i;
  361.     byte    *out_p;
  362.     cblock_t    out;
  363.     int        val;
  364.     int        j, start, max;
  365.     int        bestlength, beststart;
  366.     int        outbits;
  367.  
  368. if (in.count >= sizeof(lzss_next)/4)
  369. Error ("LZSS: too big");
  370.  
  371.     memset (lzss_head, -1, sizeof(lzss_head));
  372.  
  373.     out_p = out.data = malloc (in.count*2);
  374.     memset (out.data, 0, in.count*2);
  375.  
  376.     // write count
  377.     *out_p++ = in.count&255;
  378.     *out_p++ = (in.count>>8)&255;
  379.     *out_p++ = (in.count>>16)&255;
  380.     *out_p++ = (in.count>>24)&255;
  381.  
  382.     outbits = 0;
  383.     for (i=0 ; i<in.count ; )
  384.     {
  385.         val = in.data[i];
  386. #if 1
  387. // chained search
  388.         bestlength = 0;
  389.         beststart = 0;
  390.  
  391.         max = FRONT_WINDOW;
  392.         if (i + max > in.count)
  393.             max = in.count - i;
  394.  
  395.         start = lzss_head[val];
  396.         while (start != -1 && start >= i-BACK_WINDOW)
  397.         {            
  398.             // count match length
  399.             for (j=0 ; j<max ; j++)
  400.                 if (in.data[start+j] != in.data[i+j])
  401.                     break;
  402.             if (j > bestlength)
  403.             {
  404.                 bestlength = j;
  405.                 beststart = start;
  406.             }
  407.             start = lzss_next[start];
  408.         }
  409.  
  410. #else
  411. // slow simple search
  412.         // search for a match
  413.         max = FRONT_WINDOW;
  414.         if (i + max > in.count)
  415.             max = in.count - i;
  416.  
  417.         start = i - BACK_WINDOW;
  418.         if (start < 0)
  419.             start = 0;
  420.         bestlength = 0;
  421.         beststart = 0;
  422.         for ( ; start < i ; start++)
  423.         {
  424.             if (in.data[start] != val)
  425.                 continue;
  426.             // count match length
  427.             for (j=0 ; j<max ; j++)
  428.                 if (in.data[start+j] != in.data[i+j])
  429.                     break;
  430.             if (j > bestlength)
  431.             {
  432.                 bestlength = j;
  433.                 beststart = start;
  434.             }
  435.         }
  436. #endif
  437.         beststart = BACK_WINDOW - (i-beststart);
  438.  
  439.         if (bestlength < 3)
  440.         {    // output a single char
  441.             bestlength = 1;
  442.  
  443.             out_p[outbits>>3] |= 1<<(outbits&7);    // set bit to mark char
  444.             outbits++;
  445.             for (j=0 ; j<8 ; j++, outbits++)
  446.                 if (val & (1<<j) )
  447.                     out_p[outbits>>3] |= 1<<(outbits&7);
  448.         }
  449.         else
  450.         {    // output a phrase
  451.             outbits++;    // leave a 0 bit to mark phrase
  452.             for (j=0 ; j<BACK_BITS ; j++, outbits++)
  453.                 if (beststart & (1<<j) )
  454.                     out_p[outbits>>3] |= 1<<(outbits&7);
  455.             for (j=0 ; j<FRONT_BITS ; j++, outbits++)
  456.                 if (bestlength & (1<<j) )
  457.                     out_p[outbits>>3] |= 1<<(outbits&7);
  458.         }
  459.  
  460.         while (bestlength--)
  461.         {
  462.             val = in.data[i];
  463.             lzss_next[i] = lzss_head[val];
  464.             lzss_head[val] = i;
  465.             i++;
  466.         }
  467.     }
  468.  
  469.     out_p += (outbits+7)>>3;
  470.     out.count = out_p - out.data;
  471.     return out;
  472. }
  473.  
  474. //==========================================================================
  475.  
  476. #define    MIN_REPT    15
  477. #define    MAX_REPT    0
  478. #define    HUF_TOKENS    (256+MAX_REPT)
  479.  
  480. unsigned    charbits1[256][HUF_TOKENS];
  481. int            charbitscount1[256][HUF_TOKENS];
  482.  
  483. hnode_t        hnodes1[256][HUF_TOKENS*2];
  484. int            numhnodes1[256];
  485.  
  486. int            order0counts[256];
  487.  
  488. /*
  489. ==================
  490. SmallestNode1
  491. ==================
  492. */
  493. int    SmallestNode1 (hnode_t *hnodes, int numhnodes)
  494. {
  495.     int        i;
  496.     int        best, bestnode;
  497.  
  498.     best = 99999999;
  499.     bestnode = -1;
  500.     for (i=0 ; i<numhnodes ; i++)
  501.     {
  502.         if (hnodes[i].used)
  503.             continue;
  504.         if (!hnodes[i].count)
  505.             continue;
  506.         if (hnodes[i].count < best)
  507.         {
  508.             best = hnodes[i].count;
  509.             bestnode = i;
  510.         }
  511.     }
  512.  
  513.     if (bestnode == -1)
  514.         return -1;
  515.  
  516.     hnodes[bestnode].used = true;
  517.     return bestnode;
  518. }
  519.  
  520.  
  521. /*
  522. ==================
  523. BuildChars1
  524. ==================
  525. */
  526. void BuildChars1 (int prev, int nodenum, unsigned bits, int bitcount)
  527. {
  528.     hnode_t    *node;
  529.  
  530.     if (nodenum < HUF_TOKENS)
  531.     {
  532.         if (bitcount > 32)
  533.             Error ("bitcount > 32");
  534.         charbits1[prev][nodenum] = bits;
  535.         charbitscount1[prev][nodenum] = bitcount;
  536.         return;
  537.     }
  538.  
  539.     node = &hnodes1[prev][nodenum];
  540.     bits <<= 1;
  541.     BuildChars1 (prev, node->children[0], bits, bitcount+1);
  542.     bits |= 1;
  543.     BuildChars1 (prev, node->children[1], bits, bitcount+1);
  544. }
  545.  
  546.  
  547. /*
  548. ==================
  549. BuildTree1
  550. ==================
  551. */
  552. void BuildTree1 (int prev)
  553. {
  554.     hnode_t        *node, *nodebase;
  555.     int            numhnodes;
  556.  
  557.     // build the nodes
  558.     numhnodes = HUF_TOKENS;
  559.     nodebase = hnodes1[prev];
  560.     while (1)
  561.     {
  562.         node = &nodebase[numhnodes];
  563.  
  564.         // pick two lowest counts
  565.         node->children[0] = SmallestNode1 (nodebase, numhnodes);
  566.         if (node->children[0] == -1)
  567.             break;    // no more
  568.  
  569.         node->children[1] = SmallestNode1 (nodebase, numhnodes);
  570.         if (node->children[1] == -1)
  571.             break;
  572.  
  573.         node->count = nodebase[node->children[0]].count + 
  574.             nodebase[node->children[1]].count;
  575.         numhnodes++;
  576.     }
  577.     numhnodes1[prev] = numhnodes-1;
  578.     BuildChars1 (prev, numhnodes-1, 0, 0);
  579. }
  580.  
  581.  
  582. /*
  583. ==================
  584. Huffman1_Count
  585. ==================
  586. */
  587. void Huffman1_Count (cblock_t in)
  588. {
  589.     int        i;
  590.     int        prev;
  591.     int        v;
  592.     int        rept;
  593.  
  594.     prev = 0;
  595.     for (i=0 ; i<in.count ; i++)
  596.     {
  597.         v = in.data[i];
  598.         order0counts[v]++;
  599.         hnodes1[prev][v].count++;
  600.         prev = v;
  601. #if 1
  602.         for (rept=1 ; i+rept < in.count && rept < MAX_REPT ; rept++)
  603.             if (in.data[i+rept] != v)
  604.                 break;
  605.         if (rept > MIN_REPT)
  606.         {
  607.             hnodes1[prev][255+rept].count++;
  608.             i += rept-1;
  609.         }
  610. #endif
  611.     }
  612. }
  613.  
  614.  
  615. /*
  616. ==================
  617. Huffman1_Build
  618. ==================
  619. */
  620. byte    scaled[256][HUF_TOKENS];
  621. void Huffman1_Build (FILE *f)
  622. {
  623.     int        i, j, v;
  624.     int        max;
  625.     int        total;
  626.  
  627.     for (i=0 ; i<256 ; i++)
  628.     {
  629.         // normalize and save the counts
  630.         max = 0;
  631.         for (j=0 ; j<HUF_TOKENS ; j++)
  632.         {
  633.             if (hnodes1[i][j].count > max)
  634.                 max = hnodes1[i][j].count;
  635.         }
  636.         if (max == 0)
  637.             max = 1;
  638.         total = 0;
  639.         for (j=0 ; j<HUF_TOKENS ; j++)
  640.         {    // easy to overflow 32 bits here!
  641.             v = (hnodes1[i][j].count*(double)255+max-1)/max;
  642.             if (v > 255)
  643.                 Error ("v > 255");
  644.             scaled[i][j] = hnodes1[i][j].count = v;
  645.             if (v)
  646.                 total++;
  647.         }
  648.         if (total == 1)
  649.         {    // must have two tokens
  650.             if (!scaled[i][0])
  651.                 scaled[i][0] = hnodes1[i][0].count = 1;
  652.             else
  653.                 scaled[i][1] = hnodes1[i][1].count = 1;
  654.         }
  655.  
  656.         BuildTree1 (i);
  657.     }
  658.  
  659. #if 0
  660.     // count up the total bits
  661.     total = 0;
  662.     for (i=0 ; i<256 ; i++)
  663.         for (j=0 ; j<256 ; j++)
  664.             total += charbitscount1[i][j] * hnodes1[i][j].count;
  665.  
  666.     total = (total+7)/8;
  667.     printf ("%i bytes huffman1 compressed\n", total);
  668. #endif
  669.  
  670.     fwrite (scaled, 1, sizeof(scaled), f);
  671. }
  672.  
  673. /*
  674. ==================
  675. Huffman1
  676.  
  677. Order 1 compression with pre-built table
  678. ==================
  679. */
  680. cblock_t Huffman1 (cblock_t in)
  681. {
  682.     int            i;
  683.     int            outbits, c;
  684.     unsigned    bits;
  685.     byte        *out_p;
  686.     cblock_t    out;
  687.     int            prev;
  688.     int            v;
  689.     int            rept;
  690.  
  691.     out_p = out.data = malloc(in.count*2 + 1024);
  692.     memset (out_p, 0, in.count*2+1024);
  693.  
  694.     // write count
  695.     *out_p++ = in.count&255;
  696.     *out_p++ = (in.count>>8)&255;
  697.     *out_p++ = (in.count>>16)&255;
  698.     *out_p++ = (in.count>>24)&255;
  699.  
  700.     // write bits
  701.     outbits = 0;
  702.     prev = 0;
  703.     for (i=0 ; i<in.count ; i++)
  704.     {
  705.         v = in.data[i];
  706.  
  707.         c = charbitscount1[prev][v];
  708.         bits = charbits1[prev][v];
  709.         if (!c)
  710.             Error ("!bits");
  711.         while (c)
  712.         {
  713.             c--;
  714.             if (bits & (1<<c))
  715.                 out_p[outbits>>3] |= 1<<(outbits&7);
  716.             outbits++;
  717.         }
  718.  
  719.         prev = v;
  720. #if 1
  721.         // check for repeat encodes
  722.         for (rept=1 ; i+rept < in.count && rept < MAX_REPT ; rept++)
  723.             if (in.data[i+rept] != v)
  724.                 break;
  725.         if (rept > MIN_REPT)
  726.         {
  727.             c = charbitscount1[prev][255+rept];
  728.             bits = charbits1[prev][255+rept];
  729.             if (!c)
  730.                 Error ("!bits");
  731.             while (c)
  732.             {
  733.                 c--;
  734.                 if (bits & (1<<c))
  735.                     out_p[outbits>>3] |= 1<<(outbits&7);
  736.                 outbits++;
  737.             }
  738.             i += rept-1;
  739.         }
  740. #endif
  741.     }
  742.  
  743.     out_p += (outbits+7)>>3;
  744.  
  745.     out.count = out_p - out.data;
  746.  
  747.     return out;
  748. }
  749.  
  750. #endif
  751.